package week01

// 25. K 个一组翻转链表
// https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

// 思路:
// 1、每次获取 K 个节点作为一段
// 2、翻转本段链表
// 3、上一段链表尾节点的 Next 指向翻转后链表的头节点

// 细节：
// 1、节点不足 K 个不翻转
// 2、getTail 参数要传 K-1，因为 K 个节点为一组是跳 K-1 次
// 3、getTail == nil 的时候，记得把链表剩余部分接上去
// 4、reverseList 跟翻转链表那题不同，返回的是输入链表的 Head 节点，不是 Tail 节点
// 5、reverseList 注意处理 Tail 的 Next 节点
// 6、翻转后，原来的 Tail 变成了 Head，原来的 Head 变成了 Tail，注释先写上，别转晕了
// 7、last 是上一组的尾节点，更新的时候注意指向当前组的新尾节点
// 8、head 是上一组的头节点，更新的时候注意指向的是下一组的头节点，不是 head.Next

func reverseKGroup(head *ListNode, k int) *ListNode {
	var node = &ListNode{}
	var last = node
	for head != nil {
		// 分组
		// k 个为一组，指针要跳 K-1 次
		tail := getTail(head, k-1)
		if tail == nil {
			last.Next = head    // 链表剩余部分接上去
			break
		}
		// 下一组 Head
		nextGroupHead := tail.Next
		// 翻转
		selfHead := reverseList(head, tail)
		// 原来的 Tail 变成了 Head
		// 原来的 Head 变成了 Tail
		// 上一组的 Next 指向新的 Head，即 getTail 获取到的 Tail
		last.Next = tail
		// 保存当前组 Tail
		last = selfHead
		// 下一组重复操作
		head = nextGroupHead
	}

	return node.Next
}

func getTail(head *ListNode, k int) *ListNode {
	// 剩余节点不足 K 个，返回 nil
	// 剩余节点大于 K 个，返回第 K 个节点
	// 剩余节点刚好 K 个，返回最后一个节点
	for k > 0 {
		head = head.Next
		k--
	}
	return head
}

func reverseList(head, tail *ListNode) *ListNode {
	if head == tail {
		return head
	}
	var oldHead = head
	var last *ListNode
	for head != tail {
		next := head.Next
		head.Next = last
		last = head
		head = next
	}
	tail.Next = last
	return oldHead
}

type ListNode struct {
	Val int
	Next *ListNode
}